package com.sicheng.lc.周赛.分类.栈.单调栈or单调队列;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/25 22:32
 */
public class 找到所有好下标 {
    //https://leetcode.cn/problems/find-all-good-indices/
    static int N = (int) 1e5;
    static int[] l = new int[N + 1];
    static int[] r = new int[N + 1];
    static int n;

    public List<Integer> goodIndices(int[] nums, int k) {
        ArrayList<Integer> res = new ArrayList<>(16);
        n = nums.length;
        for (int i = 0, j = n - i - 1; i < n; i++, j--) {
            l[i] = 1;
            r[j] = 1;
            if (i > 0 && nums[i] <= nums[i - 1])
                l[i] = l[i - 1] + 1;
            if (j < n - 1 && nums[j] <= nums[j + 1])
                r[j] = r[j + 1] + 1;
        }
        for (int i = k; i < n - k; i++) {
            if (l[i - 1] >= k && r[i + 1] >= k)
                res.add(i);
        }
        return res;
    }

    public static void main(String[] args) {
        找到所有好下标 s = new 找到所有好下标();
        int[] nums = {2, 1, 1, 1, 3, 4, 1};
        int k = 2;
        System.out.println(s.goodIndices(nums, k));
    }
}
